package subject;

/**
 * 异或问题
 */
public class XOR {

    /*
    * 已知一个数组中有一个数出现了奇数词，其他数都是偶数次。请问这个数是什么
    * */
    public static void solve(int [] arrs){
        int eor = 0;
        for (int i = 0; i < arrs.length; i++) {
            eor = eor ^ arrs[i];
        }
        System.out.println(eor);
    }

    /*
     * 已知一个数组中有两个数出现了奇数次，其他数都是偶数次。请问这两个数是什么
     * */
    public static void solve2(int [] arrs){

        //假设这两个数a,b,其他均出现了偶数次
        int eor = 0;
        for (int i = 0; i < arrs.length; i++) {
            eor = eor ^ arrs[i]; //这一步完了eor就是a^b
        }

        /*
        * 这里比较难理解，因为由题意得a和b是不相等得两个数，那么就是在二进制数中，a和b肯定是有某一位是不相等的，那么这一步就是取出那一位数
        * 假设eor = 1001010
        * 那么~eor = 0110101
        * ~eor + 1 = 0110110
        * eor & (~eor +1) = 000010  取得是最右一位不相同的数
        * */
        int rightone = eor & (~eor +1);
        int onlyOne = 0;
        for (int arr : arrs) {
            //将数组分成两列，a和b也别分成两列中了。
            if ((arr & rightone) ==0){
                onlyOne ^= arr; //得出onlyone就是a或者b，因为其他都是偶数次
            }
        }
        //最后再由eor异或onlyone得出另一个数
        System.out.println(onlyOne + "," + (eor ^ onlyOne));
    }

    public static void main(String[] args) {
        int[] arrs1 = {1,2,2,4,4,4,4};
        solve(arrs1);

        int[] arrs2 = {1,2,2,4,4,4,4,5};
        solve2(arrs2);
    }
}
